/* Crackling Fire - C functional - Shawn C. Dodd */
#include <stdio.h>

#define KINK_LEN 16
#define PUZZLE_LEN 27
#define PROXIMITY 2		/* how close to origin to qualify? */

typedef struct {
	int x, y, z;
} point;

const int kink_index[KINK_LEN] = {2,3,4,6,7,9,10,11,13,15,16,17,18,20,22,24};
const int kink_map[PUZZLE_LEN] = {0,0,1,1,1,0,1,1,0,1,1,1,0,1,0,1,1,1,1,0,1,0,1,0,1,0,0};

typedef struct {				/* State of rotation of the puzzle's blocks. */
	int array[KINK_LEN];
} twists;

typedef struct {				/* Coordinates of the puzzle blocks in 3D space. */
	point coord[PUZZLE_LEN];
} puzzle;

typedef struct {				/* Puzzle coords packaged with return code. */
	puzzle p;
	int abandon;
} puzzle_ret;

const point units[6] = {		/* The unit vectors. */
	{1,0,0},  /* 0 */
	{0,1,0},  /* 1 */
	{0,0,1},  /* 2 */
	{-1,0,0}, /* 3 */
	{0,-1,0}, /* 4 */
	{0,0,-1}  /* 5 */
};

const int rotations[6][4] = {	/* Rotations of the unit vectors. */
	{2,1,5,4},
	{0,2,3,5},
	{1,0,4,3},
	{5,4,2,1},
	{3,5,0,2},
	{4,3,1,0}
};

/* ------------------------------------------------------------------------------ */

/* 
Is this puzzle a valid solution? Returns:
	-1	abandon this path
	0	continue, not a solution
	1	solution found
*/
int validate( const int depth, const puzzle p ) {return 0;}

void print_point( const point coord ) {
	printf("{%d,%d,%d}", coord.x, coord.y, coord.z);
}

void print_puzzle( const puzzle puz ) {
	int i;
	printf("{ ");
	for( i=0; i<PUZZLE_LEN; i++ ) {
		print_point( puz.coord[i] );
		if(i<PUZZLE_LEN-1) printf(", ");
	}
	printf(" }, \n");
}

int hasCollision( int startFrom, const int compareTo, const puzzle * const p ) { 
	for( ; startFrom>=0; startFrom-- )
	{
		if(	(p->coord[compareTo].x == p->coord[startFrom].x) 
			&& (p->coord[compareTo].y == p->coord[startFrom].y) 
			&& (p->coord[compareTo].z == p->coord[startFrom].z) ) {
			return 1;
		}
	}
	return 0;
}

/* 
Projects the given twists onto the puzzle and prints message if solution found. Returns .abandon:
	0	ok
	1	abandon this path
*/
puzzle_ret project( const int depth, const twists t, const puzzle p ) {
	puzzle_ret ret = {.p=p, .abandon=0};
	const int starting = kink_index[depth];
	int i,j;
	int orientation;
	int d;
	
	orientation = 0;
	d = 0;
	for( i=0; i<PUZZLE_LEN-1; i++ ) {
		if(kink_map[i]) {
			orientation = rotations[orientation][t.array[d++]];
		}
		/* TODO  replace with pre-compiler macro */
		ret.p.coord[i+1].x = ret.p.coord[i].x + units[orientation].x;
		ret.p.coord[i+1].y = ret.p.coord[i].y + units[orientation].y;
		ret.p.coord[i+1].z = ret.p.coord[i].z + units[orientation].z;
		
		/* TODO  Add optional optimization here: return if i<starting, and filter spurious sol'ns later */
		
		/* test for proximity */
		if(	abs( ret.p.coord[i+1].x - 1 ) > 1
			|| abs(ret.p.coord[i+1].y - 1 ) > 1
			|| abs(ret.p.coord[i+1].z - 1 ) > 1 ) {
			if(i==starting) {
				ret.abandon = 1;
			}
			return ret;
		}
		
		/* test for collision */
		if( i > 2 && hasCollision(i-1, i+1, &ret.p) ) {
			if(i==starting) {
				ret.abandon = 1;
			}
			return ret;
		}
	}

	for( j=0; j<KINK_LEN; j++ ) printf("%d ", t.array[j]); printf("!\n");
	print_puzzle(ret.p);
	
	return ret;
}

/*
Tries all the possible rotations at the given depth and below and prints message if solution found.
*/
void rotate( const int depth, const twists t, const puzzle p ) {
	int spin;
	if( depth==KINK_LEN) return;
	for( spin=0; spin<4; spin++ ) {
		twists tprime = t;
		tprime.array[depth] = spin;
		puzzle_ret pprime = project( depth, tprime, p );
		if( !pprime.abandon ) {
			rotate( depth+1, tprime, pprime.p );
		}
	}
}

int main (int argc, const char * argv[]) {
    const twists t = {.array = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}};
	const puzzle p = {
		.coord[ 0] = {0,0,0}, .coord[ 1] = {0,0,0}, .coord[ 2] = {0,0,0},
		.coord[ 3] = {0,0,0}, .coord[ 4] = {0,0,0}, .coord[ 5] = {0,0,0},
		.coord[ 6] = {0,0,0}, .coord[ 7] = {0,0,0}, .coord[ 8] = {0,0,0},
		.coord[ 9] = {0,0,0}, .coord[10] = {0,0,0}, .coord[11] = {0,0,0},
		.coord[12] = {0,0,0}, .coord[13] = {0,0,0}, .coord[14] = {0,0,0},
		.coord[15] = {0,0,0}, .coord[16] = {0,0,0}, .coord[17] = {0,0,0},
		.coord[18] = {0,0,0}, .coord[19] = {0,0,0}, .coord[20] = {0,0,0},
		.coord[21] = {0,0,0}, .coord[22] = {0,0,0}, .coord[23] = {0,0,0},
		.coord[24] = {0,0,0}, .coord[25] = {0,0,0}, .coord[26] = {0,0,0}
	};
	
	rotate(0, t, p);
    return 0;
}
